1. Field of the Invention
The present invention relates to a cryptographic communication method, encryption method, and cryptographic communication system that afford a high level of safety in encryption and communication of information by utilizing information encrypted in such a manner not to be understood by anyone but the intended persons.
2. Description of the Related Art
In today""s society, sometimes called the advanced information society, documents and graphic information that are important for business are transmitted and processed in the form of electronic information, using a computer network as a platform. By its nature, this electronic information is easy to duplicate, making it hard to tell an original from a copy, and information security has therefore become an important issue. In particular, building a computer network that satisfies the requirements of xe2x80x9cshared computer resources,xe2x80x9d xe2x80x9cmulti-access,xe2x80x9d and xe2x80x9cbroad area networkingxe2x80x9d is essential to the establishment of a true highly sophisticated information society, but this includes factors that are in conflict with the goal of information security between involved parties. Encryption technology, which has been used primarily for military and diplomatic purposes in past human history, is attracting attention as an effective means for resolving this conflict.
Cryptography deals with exchanging information in such a way that the meaning thereof cannot be understood by anyone but the intended recipient. In cryptography, converting original text that can be understood by anyone (plaintext) into text that is meaningless to a third party (ciphertext) is called encryption, while returning the ciphertext to the original plaintext is called decryption, and the overall process of this encryption and decryption is called a cryptosystem. Secret encryption and decryption keys are used in the process of encryption and decryption, respectively. Since a secret decryption key is necessary during decryption, only someone who knows this decryption key can decrypt a ciphertext, so encryption allows the confidentiality of information to be preserved.
An encryption key may be the same as or different from a decryption key. A cryptosystem in which the two keys are the same is called a common or shared key cryptosystem, and the DES (Data Encryption Standards) employed by the Bureau of Standards of the US Department of Commerce is a typical example of this. Public key cryptosystems are proposed as an example of a cryptosystem in which the two keys are different. With a public key cryptosystem, each user (entity) that utilizes the cryptosystem generates a pair of keys, i.e., an encryption key and a decryption key, discloses the encryption key on a public key list, and keeps just the decryption key secret. An advantage of a public key cryptosystem is that the paired encryption key and decryption key are different and a one-way function is utilized, which makes it impossible for someone to deduce the decryption key from the encryption key.
A public key cryptosystem is a revolutionary cryptosystem in which the encryption key is disclosed, and satisfies the above three requirements necessary for the establishment of a sophisticated information society. A great deal of research has gone into these systems in an effort to utilize them in such fields as information communication technology, and a typical public key cryptosystem that has been proposed is the RSA cryptosystem. This RSA cryptosystem makes use of the difficulty of factoring large prime numbers using one-way functions. There are also public key cryptosystems that make use of the difficulty of solving discrete logarithm problems.
There is also a cryptosystem that makes use of personal ID (identity) information, such as the name or address of each entity. With this cryptosystem, a shared encryption key is generated between the sender and recipient on the basis of ID information. Cryptographic methods based on this ID information include (1) those that require pre-communication between the sender and recipient prior to the transmission of the ciphertext, and (2) those that do not require pre-communication between the sender and recipient prior to the transmission of the ciphertext. Since the second type of method does not require any pre-communication, it is very convenient for an entity, and is expected to become a mainstay of cryptosystems in the future.
The second type of scheme is called ID-NIKS (an ID-based non-interactive key sharing scheme), in which an encryption key is shared, without any pre-communication being performed, by using ID information about the communicating party. ID-NIKS does not require that a public key and secret key be exchanged between the sender and recipient, nor does it require a key list or service by a third party, allowing secure communication between any entities.
FIG. 9 of the accompanying drawings is a diagram showing the principle behind this ID-NIKS system The existence of a center that can be trusted is assumed, and a common key generation system is built around this center. In this diagram, ID information such as the name, address, and telephone number of an entity X, which is personal information of entity X, is expressed as h(IDx) using a hash function h(xc2x7). The center calculates secret information Sxi as follows on the basis of public center information {PCi}, secret center information (SCi}, and entity X ID information h(IDx), and secretly distributes this calculated information to entity X.
Sxi=Fi({SCi}, {PCi}, h(IDx))
For communication with any other entity Y, entity X uses his own secret information {SXi}, public center information {PCi}, and the other entity Y ID information h(IDY) to generate a common key KXY for encryption and decryption as follows.
KXY=f({SXi}, {PCi}, h(IDY))
Similarly, entity Y also generates a common key KYX for entity X. As long as the relationship KXY=KYX holds true, then these keys KXY and KYX can be used as an encryption key and decryption key between entities X and Y.
With the public key cryptosystems discussed above, in the case of an RSA cryptosystem, for instance, this public key is over ten times as long as current telephone numbers, and is therefore far from simple. In contrast, with an ID-NIKS system, if each set of ID information is registered in the form of a roster, then a public key can be generated between itself and any other entity by referring to this roster. Therefore, if the ID-NIKS illustrated in FIG. 9 could be safely implemented, it would be possible to construct a convenient cryptosystem over a computer network to which many entities subscribe. It is for this reason that an ID-NIKS system is expected to be at the forefront of future cryptosystems.
It is preferable for ID-NIKS, in which common keys that serve as encryption and decryption keys are mutually shared by using the ID information of the communicating parties without any pre-communication being performed, to be sufficiently secure against attack involving a collusion of a plurality of entities, for example. However, this ID-NIKS has the problem that the secret parameters of the center can be revealed if enough people (entities) are in collusion since such attack method has been studied. Whether a cryptologically safe ID-NIKS system can be constructed is an important question for a sophisticated information society, and a search is underway for a more ideal encryption system.
An object of the present invention is to provide a novel cryptographic communication method and cryptographic communication system involving ID-NIKS system, with which secret key generation functions and key sharing functions are not separable, key sharing is probabilistically possible, and high degree of security is realized.
According to the first aspect of the present invention, there is provided a cryptographic communication method for communication of information between entities, in which a center generates and sends an entity-specific secret key to each entity, one entity uses a common key determined from its own entity-specific secret key sent from the center and a publicly known public key of the other entity to encrypt a plaintext into a ciphertext and transmits it to the other entity, and the other entity uses the same common key as the above-mentioned common key, determined from the second entity-specific secret key sent from the center to the other entity (the-other-entity-specific secret key) and the disclosed public key of the one entity, to decrypt the ciphertext back into a plaintext, characterized in that each-entity-specific secret key includes plural types of secret keys in which each of a plurality of numbers serves as a modulus, said plural types of secret keys being generated using respective entities"" public keys and entity-specific random numbers, one entity uses a plural types of its own secret keys and the public key of the other entity or entities to generate the common key, and the other entity or entities use a plurality of its own secret keys and the public key of the one entity to generate said common key.
In the generation of the common key, the random number may be eliminated by addition over integer ring.
The random number may be a multidimensional random number vector.
The computational formulas for generating two types of the secret keys at the center may be as follows.
{right arrow over (si)}=(A{right arrow over (vi)}+{right arrow over (xcex3i)})mod P
{right arrow over (ti)}=(B{right arrow over (vi)}xe2x88x92{right arrow over (xcex3i)})mod Q
Where
Vector si: one secret key of entity i
Vector ti: the other secret key of entity i
P and Q: publicly known prime numbers
A and B: symmetric matrices composed of random numbers known only to the center
Vector xcex3i: a personal random number vector composed of random numbers
The computational formulas for generating the common key for the entities may be as follows.
Aijxe2x80x2=t{right arrow over (si)}{right arrow over (vj)} mod P
Bijxe2x80x2=t{right arrow over (ti)}{right arrow over (vj)} mod Q
Kij=Aijxe2x80x2+Bijxe2x80x2
Where
Kij: common key generated by one entity i for another entity j
Vector vj: public key of entity j
Aijxe2x80x2 and Bijxe2x80x2: intermediate values for generating the common key Kij 
k bits of the P and Q may be employed to satisfy the following formulas.
Pxe2x89xa1xcex4(mod R)
Qxe2x89xa1xcex5(mod R)
Where
R: prime number of d bits
xcex4 and xcex5: number of e bits
k greater than d greater than e
The computational formulas for generating the common key for the entities may be given by the following equations.
Kijxe2x80x2=Aijxe2x80x2+Bijxe2x80x2
Kijxe2x80x3=Kijxe2x80x2mod R
            A      ij      xe2x80x2        =                                       t                ⁢                              s            i                    →                    ⁢                        υ          j                →            ⁢      mod      ⁢              xe2x80x83            ⁢      P                  B      ij      xe2x80x2        =                                       t                ⁢                              t            i                    →                    ⁢                        υ          j                →            ⁢      mod      ⁢              xe2x80x83            ⁢      Q                  K      ij        =          ⌊                        K          ij          xe2x80x3                          2                      e            +            c                              ⌋      
Where
Kij: common key generated by one entity i for another entity j
Kijxe2x80x2: an intermediate value for generating the common key Kij 
Kijxe2x80x3: an intermediate value for generating the common key Kij, i.e., remainder of dividing Kijxe2x80x2 by R
The public key for each entity may be determined by utilizing a hash function to calculate the each entity-specific information.
According to the second aspect of the present invention, there is provided an encryption method, in which secrets keys are sent to a plurality of entities, said secret keys being specific to the entities to which they are sent, and said entities use their own said entity specific keys to encrypt a plaintext into a ciphertext, characterized in that each-entity-specific secret key includes plural types of secret keys in which each of a plurality of numbers serves as a modulus, said plural types of secret keys being generated using its own entity-specific public key and its own entity-specific secret random number, and one entity encrypts a plaintext into a ciphertext using a common key generated using its own plural types of secret keys and a public key of the other entity, who is the intended recipient of the ciphertext.
According to the third aspect of the present invention, there is provided a cryptographic communication system including a plurality of entities, in which encryption into a ciphertext of a plaintext to be transmitted and decryption of the transmitted ciphertext back into an original plaintext are performed mutually between the plurality of entities, characterized in that the cryptographic communication system includes: a center that uses each-entity-specific public key and each-entity-specific secret random number to generate for each entity a plurality of types of secret keys in which each of a plurality of numbers serves as a modulus in relation to the plurality of types of secret keys, and sends these secret keys to each entity; and a plurality of entities, one of which uses a plurality of its own type of secret keys sent from the center and another-entity-specific public key to generate a common key for performing the encryption, and another of which uses a plurality of its own type of secret keys sent from the cente and an entity-specific key of the one entity for performing the decryption. The xe2x80x9canother entityxe2x80x9d is an entity which receives the ciphertext and decrypts it into the original plaintext.
According to the fourth aspect of the present invention, there is provided a cryptographic communication method for the communication of information between entities, in which an entity-specific secret key is generated by a center and sent to each entity from the center, one entity utilizes a common key determined from its own entity-specific secret key sent from the center and a publicly known public key of the other entity to encrypt a plaintext into a ciphertext and transmits it to the other entity, and the other entity utilizes the same common key as the above-mentioned common key, said common key being determined from its own entity-specific secret key sent from the center and the disclosed public key of the other entity, to decrypt the ciphertext back into a plaintext, characterized in that each entity-specific secret key includes a plurality of secret keys in which each of a plurality of numbers serves as a modulus, said plurality of secret keys being generated using a plurality of public keys of each entity and a plurality of each entity-specific random numbers, and each entity uses its own multiple secret keys and the plurality of public keys of the other entity to generate the common key.
When the common key is produced, the plurality of random numbers may be eliminated by addition over integer ring.
The plurality of random numbers may be a plurality of multidimensional random number vectors.
The computational formula for generating four secret keys at the center may be an equation (A) below, and the computational formula for generating the common key at each entity may be an equation (B) below.                                                                                                               s                                          11                      ,                      i                                                        →                                =                                                      (                                                                                            A                          1                                                ⁢                                                                              υ                                                          1                              ,                              i                                                                                →                                                                    +                                                                        γ                                                      1                            ,                            i                                                                          →                                                              )                                    ⁢                  mod                  ⁢                                      xe2x80x83                                    ⁢                                      P                    1                                                                                                                                                                s                                          22                      ,                      i                                                        →                                =                                                      (                                                                                            A                          2                                                ⁢                                                                              υ                                                          2                              ,                              i                                                                                →                                                                    +                                                                        γ                                                      2                            ,                            i                                                                          →                                                              )                                    ⁢                  mod                  ⁢                                      xe2x80x83                                    ⁢                                      P                    2                                                                                                                                                                s                                          21                      ,                      i                                                        →                                =                                                      (                                                                                            A                          3                                                ⁢                                                                              υ                                                          1                              ,                              i                                                                                →                                                                    -                                                                        γ                                                      2                            ,                            i                                                                          →                                                              )                                    ⁢                  mod                  ⁢                                      xe2x80x83                                    ⁢                                      P                    3                                                                                                                                                                s                                          12                      ,                      i                                                        →                                =                                                                            (                      t                                        ⁢                                                                                            A                          3                                                ⁢                                                                              υ                                                          2                              ,                              i                                                                                →                                                                    -                                                                        γ                                                      1                            ,                            i                                                                          →                                                              )                                    ⁢                  mod                  ⁢                                      xe2x80x83                                    ⁢                                      P                    3                                                                                      }                            (        A        )            
Where
Vector S11,i: first secret key of entity i
Vector S22,i: second secret key of entity i
Vector S21,i: third secret key of entity i
Vector S12,i: fourth secret key of entity i
Vector v1,i: first public key of entity i
Vector v2,i: second public key of entity i
P1, P2, and P3: publicly known prime numbers
A1 and A2: secret symmetric matrices composed of random numbers known only to the center
A3: secret matrix composed of random numbers known only to the center
Vector xcex31,i: first personal random number vector composed of random numbers
Vector xcex32,i: second personal random number vector composed of random numbers
Kij=A11,ijxe2x80x2+A22,ijxe2x80x2+A21,ijxe2x80x2+A12,ijxe2x80x2xe2x80x83xe2x80x83(B)
  "AutoLeftMatch"      (                                                      A                              11                ,                ij                            xe2x80x2                        =                                                                               t                                ⁢                                                      s                                          11                      ,                      i                                                        →                                            ⁢                                                υ                                      1                    ,                    j                                                  →                            ⁢              mod              ⁢                              xe2x80x83                            ⁢                              P                1                                                                                                    A                              22                ,                ij                            xe2x80x2                        =                                                                               t                                ⁢                                                      s                                          22                      ,                      i                                                        →                                            ⁢                                                υ                                      2                    ,                    j                                                  →                            ⁢              mod              ⁢                              xe2x80x83                            ⁢                              P                2                                                                                                    A                              21                ,                ij                            xe2x80x2                        =                                                                               t                                ⁢                                                      s                                          21                      ,                      i                                                        →                                            ⁢                                                υ                                      2                    ,                    j                                                  →                            ⁢              mod              ⁢                              xe2x80x83                            ⁢                              P                3                                                                                                    A                              12                ,                ij                            xe2x80x2                        =                                                                               t                                ⁢                                                      s                                          12                      ,                      i                                                        →                                            ⁢                                                υ                                      1                    ,                    j                                                  →                            ⁢              mod              ⁢                              xe2x80x83                            ⁢                              P                3                                                          )  
Where
Kij: common key generated by one entity i for another entity j
Vector v1,j: first public key of entity j
Vector v2,j: second public key of entity j
A11,ijxe2x80x2, A22,ijxe2x80x2, A21,ijxe2x80x2, and A12,ijxe2x80x2: intermediate values for generating the common key Kij 
There may be d number of public keys for each entity, the computational formula for generating d2 number of the secret keys at the center is as follows (C), and the computational formula for generating the common key at each entity is as follows (D).                                           s                          yz              ,              i                                →                =                              (                                                            A                  yz                                ⁢                                                      υ                                          z                      ,                      i                                                        →                                            +                                                γ                                      yz                    ,                    i                                                  →                                      )                    ⁢          mod          ⁢                      xe2x80x83                    ⁢                      P            yz                                              (        C        )            
Where
Ayz (y and z=1, 2, . . . , d): a sub-matrix generated by partitioning an nxc3x97n symmetric matrix A in both the row and column directions at n1, n2, . . . , nd (where n=n1+n2+ . . . +nd)
Vector Syz,i: d2 number of secret keys of entity i
Vector vz,i: a vector generated by dividing a public key column vector vi of entity i in the column direction into sizes of n1, n2, . . . , nd 
Vector xcex3yz,i: a vector generated by dividing a personal random number column vector xcex3z,i of entity i in the column direction into sizes of n1, n2, . . . , nd 
Pyz: publicly known prime number                               K          ij                =                              ∑                          y              =              1                        d                    ⁢                                    ∑                              z                =                1                            d                        ⁢                                          A                                  yz                  ,                  ij                                xe2x80x2                            ⁡                              (                                                      A                                          yz                      ,                      ij                                        xe2x80x2                                    =                                                                                                             t                                            ⁢                                                                        s                                                      yz                            ,                            i                                                                          →                                                              ⁢                                                                  υ                                                  y                          ,                          j                                                                    →                                        ⁢                    mod                    ⁢                                          xe2x80x83                                        ⁢                                          P                      yz                                                                      )                                                                        (        D        )            
Where
Kij: common key generated by one entity i for another entity j
Vector vy,j: a vector generated by dividing a public key row vector vj of entity i in the row direction into sizes of n1, n2, . . . , nd 
Ayz,ijxe2x80x2: d2 number of intermediate values for generating the common key Kij 
A plurality of combinations may be used in which each combination includes d number of the public keys for each entity, and d2 number of the secret keys for each entity.
The computational formula for generating 2d number of the secret keys at the center is as follows (E), and the computational formula for generating the common key at each entity is as follows (F).                                                                                                               s                                          r                      ,                      i                                                        →                                =                                                      (                                                                                            A                          r                                                ⁢                                                                              υ                                                                                          r                                +                                1                                                            ,                              i                                                                                →                                                                    +                                                                        γ                                                      r                            ,                            i                                                                          →                                                              )                                    ⁢                  mod                  ⁢                                      xe2x80x83                                    ⁢                                      P                    r                                                                                                                                                                t                                          r                      ,                      i                                                        →                                =                                                      (                                                                                            B                          r                                                ⁢                                                                              υ                                                          r                              ,                              i                                                                                →                                                                    -                                                                        γ                                                                                    r                              +                              1                                                        ,                            i                                                                          →                                                              )                                    ⁢                  mod                  ⁢                                      xe2x80x83                                    ⁢                                      P                    r                                                                                      }                            (        E        )            
Where
Vector Sr,i: d number of secret keys of entity i
Vector tr,i: d number of secret keys of entity i
Ar: a secret matrix composed of random numbers known only to the center
Br=tAr 
Vector Vr,i: d number of public keys of entity i
Vector xcex3r,i: d number of personal random number vectors composed of random numbers
Pr: publicly known prime number                                           K            ij                    =                                    ∑                              r                =                1                            d                        ⁢                          (                                                A                                      r                    ,                    ij                                    xe2x80x2                                +                                  B                                      r                    ,                    ij                                    xe2x80x2                                            )                                      ⁢                  
                ⁢                  (                                                                                          A                                          r                      ,                      ij                                        xe2x80x2                                    =                                                                                                             t                                            ⁢                                                                        s                                                      r                            ,                            i                                                                          →                                                              ⁢                                                                  υ                                                  r                          ,                          j                                                                    →                                        ⁢                    mod                    ⁢                                          xe2x80x83                                        ⁢                                          P                      r                                                                                                                                                                B                                          r                      ,                      ij                                        xe2x80x2                                    =                                                                                                             t                                            ⁢                                                                        t                                                      r                            ,                            i                                                                          →                                                              ⁢                                                                  υ                                                                              r                            +                            1                                                    ,                          j                                                                    →                                        ⁢                    mod                    ⁢                                          xe2x80x83                                        ⁢                                          P                      r                                                                                                    )                                    (        F        )            
Where
Kij: common key generated by one entity i for another entity j
Vector vr,j: d number of public keys of entity j
Ar,ijxe2x80x2 and Br,ijxe2x80x2: an intermediate value for generating the common key Kij 
The plurality of public keys for each entity may be determined by utilizing a hash function to calculate the specific information of each entity.
According to the fifth aspect of the present invention, there is provided an encryption method, in which secret keys are generated at a center and sent to a plurality of entities from the center, said secret keys being specific to the entities to which they are sent, and said entities use their own said entities"" specific keys to encrypt a plaintext into a ciphertext, characterized in that each-entity-specific secret key of each entity includes a plurality of secret keys in which each of a plurality of numbers serves as a modulus, said plurality of secret keys being generated using a plurality of its own entity-specific public keys and a plurality of its own entity-specific secret random numbers, and one entity encrypts a plaintext into a ciphertext using a common key generated using these plurality of its own secret keys and a plurality of public keys of the other entity, who is the intended recipient of the ciphertext.
According to the sixth aspect of the present invention, there is provided a cryptographic communication system, in which encryption into a ciphertext of a plaintext to be transmitted, and decryption of the transmitted ciphertext back into a plaintext, are performed mutually between a plurality of entities, characterized in that the cryptographic communication system includes a center for using a plurality of each-entity-specific public keys and a plurality of each-entity-specific secret random numbers to generate for each entity a plurality of secret keys in which each of a plurality of numbers serves as a modulus, and for sending these plural secret keys to each entity, and a plurality of entities each of which uses its own plural secret keys sent from the center and a plurality of public keys specific to another entity, who is an entity to receive a ciphertext or an entity to send a ciphertext, to generate a common key for performing the encryption processing and decryption processing.
First, let us discuss the conditions for realizing an ID-NIKS system, and the conditions for secure ID-NIKS. Here, i, j, y, and z express entities, vi is the public key of entity i which in most cases is the ID hash value, si is the secret key of entity i, and Kij is the common key with entity j determined by entity i.
The following three conditions must be met for an ID-NIKS system to be realized.
Condition 1 (Secret Key Generation Condition)
The center is able to determine the corresponding secret key si from the public key vi of entity i using a secret key generation function f(xc2x7).
si=f(vi)
Condition 2 (Common Key Generation Condition)
The common key Kij can be determined from the secret key si of entity i and the public key vj of entity j using a common key generation function g(xc2x7).
Kij=g(si, vj)
Condition 3 (Key Sharing Condition)
The common key Kij generated by entity i for entity j is equal to the common key Kji generated by entity j for entity i.
Kij=Kji
Therefore, a key sharing function F(xc2x7) in which the variables are vi and vj, obtained by substituting the secret key generation function f(xc2x7) into the common key generation function g(xc2x7), is a symmetric function.
F(vi, vj)=F(vj, vi)
Where F(vi, vj)=g(f(vi), (vj)=g(si, vj)
The term xe2x80x9cseparablexe2x80x9d here is defined as follows.
Definition: If we let a suitable commutative method be ◯, when the following formula is always satisfied, then the function f is separable by ◯.
f(x+y)=f(x)◯f(y)
For example, f(x)=ax and f(x)=ax are separable as shown below.
f(x+y)=a(x+y)=ax+ay=f(x)+f(y)
f(x+y)=ax+y=axxc2x7ay=f(x)xc2x7f(y)
Meanwhile, f(x)=ax+b is not separable as shown below.
f(x+y)=a(x+y)+b=ax+ay+b
f(x)+f(y)=ax+b+ay+b=ax+ay+2b
Thus, f(x+y)xe2x89xa0f(x)+f(y)
When the public key vz of an entity z that is the object of attack is expressed by linear combination of public keys vi of conspirators, and furthermore when either one of the secret key generation function or key sharing function is separable in polynomial time, then the secret key and common key of the entity can be forged without finding the center""s secrets. This method of attack has in the past been called a linear attack.
It used to be thought that it was easy to express a public key vz by linear combination, but methods have also been developed with which it is not always easy to express the public key vz of a target entity by linear combination. In view of this, linear attack should be considered as two parts: a first-stage attack portion in which the public key vz is expressed as a linear combination, and a second-stage attack portion in which the function is separated and a key is forged. In the following description, this first stage of linear attack will be distinguished by being called combination attack, while the second stage will be called separation attack. The linear attack will refer to this combination attack and separation attack jointly.
The following theorems apply for separation attack.
Theorem 1 (separation attack against secret key):
A secret key sz can be forged in polynomial time by separation attack using a secret key when a public key vz is subjected to combination attack using integer coefficients, when the secret key generation function is separable in polynomial time by an operation ◯, and when the inverse with respect to the operation ◯ is found in polynomial time.
Theorem 2 (separation attack against common key):
A common key Ky2 can be forged in polynomial time by separation attack using only a common key when a public key vz is subjected to combination attack using integer coefficients, when the secret key generation function is separable in polynomial time by an operation ◯, and when the inverse with respect to the operation ◯ is found in polynomial time.
The following conditions 4 and 5 should be met in order to build an ID-NIKS system that is secure against the separation attacks discussed above.
Condition 4 (Security of Secret Key Against Separation Attack)
It is difficult to separate the secret key generation function f in polynomial time.
Condition 5 (Security of Common Key Against Separation Attack)
It is difficult to separate the key sharing function F in polynomial time.
This condition 5 is extremely stringent, and simply means that if the functional form at the key sharing stage is separable, i.e., the key sharing function is separablexe2x96xa1C then the system is not secure, regardless of intermediate calculations. For instance, a product-sum type of ID-NIKS and a power product type of ID-NIKS do not satisfy this condition.
With the present invention, the secret key generation function and the key sharing function are inseparable, and key sharing is probabilistically possible. Inseparability is accomplished by calculation over finite fields in which a large prime number serves as the modulus, and then eliminating the random numbers by addition over integer ring. The basis of security with the present invention is that when the size of a coefficient is limited, it is difficult to express any vector by the linear combination of the vectors of the conspirators. The collusion threshold is also raised by the use of random number vectors specific to each entity.
Also, the present invention involves the use of a plurality of public keys for each entity, and these plurality of public keys are combined to eliminate random numbers, so the complexity of the random number elimination is increased and higher security is achieved. Furthermore, because the random numbers are divided, the problem of digits being carried up is ameliorated.